package cn.itcast.algorithm.exercise;

import cn.itcast.algorithm.exercise.helpclass.ListNode;

/**
 * create by zhangtian105 on 2022/5/28
 */
public class ExerciseNC78 {
    public static void main(String[] args) {
        ListNode head = new ListNode(0) ;
        ListNode data1 = new ListNode(1) ;
        ListNode data2 = new ListNode(2) ;

        head.next = data1 ;
        data1.next = data2 ;

        System.out.println(reverseList(head)); ;
    }

    /**
     * 思路：head头指针逐渐向后移动，并且将其指针反向指向其前驱节点，需要借助其他指针保存现场，不能让链表断开了
     * 使用end指针，逐渐向后遍历，保证遍历的终止条件
     * 使用now指针保存当前节点位置，避免丢失
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head ;
        }

        // 起始end指针位置与head一致
        ListNode end = head, now ;
        while (end.next != null) {
            now = head ; // now指针维护head前一个结点不丢失
            head = end.next ; // head节点通过end节点后移一位，新的头结点移动到了下一个节点
            end.next = head.next ; // 尾部节点指向head的下一个节点，将尾指针指向头指针的下一个节点
            head.next = now ; // 调转头指针，之前起一个节点，挂载一个数据节点
        }

        return head ;
    }
}
